package com.leecode.exercise;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: shubin_yao
 * @Date: 2022/06/25/22:16
 * @Description: 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
 * 输入: root = [1,3,2,5,3,null,9]
 * 输出: [1,3,9]
 */
public class LeeCode_515_MaxList {
    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(3);
        TreeNode node7 = new TreeNode(7);

        root1.left = node2;
        root1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        Solution5 solution5 = new Solution5();
        List<Integer> list = solution5.largestValues(root1);
        System.out.println(list);

    }


}

class Solution5 {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list, 1);
        return list;
    }

    //level表示的是第几层，集合res中的第一个数据表示的是第一层的最大值，第二个数据表示的是第二层的最大值……
    private void dfs(TreeNode root, List<Integer> res, int level) {
        if (root == null)
            return;
        //如果走到下一层了直接加入到集合中
        if (level == res.size() + 1) {
            res.add(root.val);
        } else {
            //注意：我们的level是从1开始的，也就是说root
            // 是第一层，而集合list的下标是从0开始的，
            // 所以这里level要减1。
            // Math.max(res.get(level - 1), root.val)表示的
            // 是遍历到的第level层的root.val值和集合中的第level
            // 个元素的值哪个大，就要哪个。
            res.set(level - 1, Math.max(res.get(level - 1), root.val));
        }
        //下面两行是DFS的核心代码
        dfs(root.left, res, level + 1);
        dfs(root.right, res, level + 1);
    }
}
